﻿#include "DoubleCircleLinedListWithHead.h"

// 带头双向循环链表-工具函数
// 构建新节点
ListNode* BuyListNode(DataType data)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		printf("节点申请失败\n");
		exit(-1);
	}
	node->next = node->prev = NULL;
	node->data = data;
}

// 带头双向循环链表-基本操作函数
// 初始化
void DoubleLinkedListInit(ListNode** pphead)
{
	assert(pphead);
	(*pphead) = BuyListNode(0);
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);
}
// 头部插入
void DoubleLinkedListPushFront(ListNode* phead, DataType elem)
{
	assert(phead);
	ListNode* node = BuyListNode(elem);
	ListNode* first = phead->next;
	node->next = first;
	first->prev = node;
	phead->next = node;
	node->prev = phead;
}
// 头部删除
void DoubleLinkedListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* first = phead->next;
	phead->next = first->next;
	first->next->prev = phead;
	free(first);
}
// 尾部插入
void DoubleLinkedListPushBack(ListNode* phead, DataType elem)
{
	assert(phead);
	ListNode* node = BuyListNode(elem);
	ListNode* tail = phead->prev;
	tail->next = node;
	node->prev = tail;
	node->next = phead;
	phead->prev = node;
}
// 尾部删除
void DoubleLinkedListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
}
// 在第pos位置的后面插入
void DoubleLinkedListInsert(ListNode* phead, size_t pos, DataType elem)
{
	assert(phead);
	assert(pos < DoubleLinkedListLength(phead));
	ListNode* node = BuyListNode(elem);
	ListNode* cur = phead->next;
	while (pos--)
	{
		cur = cur->next;
	}
	cur->next->prev = node;
	node->next = cur->next;
	cur->next = node;
	node->prev = cur;
}
// 删除第pos位置后面的元素
void DoubleLinkedListErase(ListNode* phead, size_t pos)
{
	assert(phead);
	assert(pos < DoubleLinkedListLength(phead) - 1);
	ListNode* cur = phead->next;
	while (pos--)
	{
		cur = cur->next;
	}
	ListNode* del = cur->next;
	cur->next = del->next;
	del->next->prev = cur;
	free(del);
}
// 查找指定数值的节点
ListNode* DoubleLinkedListFind(ListNode* phead, DataType elem)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == elem)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 获取链表长度
size_t DoubleLinkedListLength(ListNode* phead)
{
	assert(phead);
	size_t count = 0;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
// 正序遍历
void DoubleLinkedListTraverse(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 倒序遍历
void DoubleLinkedListRetraverse(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->prev;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->prev;
	}
	printf("\n");
}